package lfu

import (
	"go-programming-tour-book/cache"
)

type entry struct {
	key    string
	value  interface{}
	weight int //该 entry 在 queue 中权重（优先级），访问次数越多，权重越高
	index  int //该 entry 在该堆（heap）中的索引
}

func (e *entry) Len() int {
	return cache.CacLen(e.value) + 4 + 4
}

// LFU 算法用最小堆实现。在 Go 中，通过标准库 container/heap 实现最小堆，
// 要求 queue 实现 heap.Interface 接口
//
//	type Interface interface {
//		sort.Interface
//		Push(x interface{}) // add x as element Len()
//		Pop() interface{}   // remove and return element Len() - 1.
//	}
type queue []*entry

func (q queue) Len() int {
	return len(q)
}

func (q queue) Less(i, j int) bool {
	return q[i].weight < q[j].weight
}

func (q queue) Swap(i, j int) {
	q[i], q[j] = q[j], q[i]
	q[i].index = i
	q[j].index = j
}

func (q *queue) Push(x interface{}) {
	n := len(*q)
	en := x.(*entry)
	en.index = n
	*q = append(*q, en)
}

func (q *queue) Pop() interface{} {
	old := *q
	n := len(old)
	en := old[n-1]
	old[n-1] = nil // avoid memory leak
	en.index = -1  // for safety 这样做的目的是为了避免在其他地方误用或误认为该元素仍然存在于队列中，从而避免潜在的错误或逻辑上的混乱。这是一种预防性的做法，以确保代码的安全性和正确性。
	*q = old[0 : n-1]
	return en
}
